package com.yww.leetcode.binarytree;

import com.yww.leetcode.common.TreeNode;

import java.util.Arrays;

/**
 * @author yww
 * @description 106. 从中序与后序遍历序列构造二叉树
 * @since 2024/2/13 19:21
 */
public class BuildTree106 {
    // 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
    // postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    // inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) {
            return null;
        }
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal, null, null);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                int[] inorderLeft = Arrays.copyOfRange(inorder, 0, i); // 划分左子树
                int[] inorderRight = Arrays.copyOfRange(inorder, i + 1, inorder.length); // 划分右子树

                int[] postorderLeft = Arrays.copyOfRange(postorder, 0, i); // 划分左子树
                int[] postorderRight = Arrays.copyOfRange(postorder, i, postorder.length - 1); // 划分右子树
                root.left = buildTree(inorderLeft, postorderLeft);
                root.right = buildTree(inorderRight, postorderRight);
                break;
            }
        }
        return root;
    }
}
